Go 的语法树 - AST 包

Golang 中的 AST

golang 官方提供的几个包，可以帮助我们进行 AST 分析：

• go/scanner：词法解析，将源代码分割成一个个token
• go/token：token类型及相关结构体定义
• go/ast：ast的结构定义
• go/parser：语法分析，读取token流生成ast

通过上述的四个库，我们就可以实现 golang 代码的语法树分析。

Scanner 语法解析

任何编译器所做的第一步都是将源代码转换成 token，这就是 Scanner 所做的事 token 可以是关键字，字符串值，变量名以及函数名等等 在 golang 中，每个 token 都以它所处的位置，类型和原始字面量来表示

比如我们用如下代码扫描源代码的 token：

package main

import (
    "fmt"
    "go/scanner"
    "go/token"
)

var srcCode = `
package main
import "fmt"
//comment
func main() {
  fmt.Println("Hello, world!")
}
`

func main() {
    src := []byte(srcCode)
    var s scanner.Scanner
    fset := token.NewFileSet()
    file := fset.AddFile("", fset.Base(), len(src))
    s.Init(file, src, nil, 0)

    for {
        pos, tok, lit := s.Scan()
        fmt.Printf("%-6s%-8s%q\n", fset.Position(pos), tok, lit)
        if tok == token.EOF {
            break
        }
    }
}

执行 go run main.go 我们可以得到：

2:1   package "package"
2:9   IDENT   "main"
2:13  ;       "\n"
3:1   import  "import"
3:8   STRING  "\"fmt\""
3:13  ;       "\n"
5:1   func    "func"
5:6   IDENT   "main"
5:10  (       ""
5:11  )       ""
5:13  {       ""
6:3   IDENT   "fmt"
6:6   .       ""
6:7   IDENT   "Println"
6:14  (       ""
6:15  STRING  "\"Hello, world!\""
6:30  )       ""
6:31  ;       "\n"
7:1   }       ""
7:2   ;       "\n"
7:3   EOF     ""

注意没有扫描出注释，需要的话要将 s.Init 的最后一个参数改为 scanner.ScanComments。

Parser 解析 Token

• 当源码被扫描成 token 之后，结果就被传递给了 Parser
• 将 token 转换为抽象语法树（AST）
• 编译时的错误也是在这个时候报告的

来看如下的例子：

func TestParserAST(t *testing.T) {
    src := []byte(`/*comment0*/
package main
import "fmt"
//comment1
/*comment2*/
func main() {
  fmt.Println("Hello, world!")
}
`)

    // Create the AST by parsing src.
    fset := token.NewFileSet() // positions are relative to fset
    f, err := parser.ParseFile(fset, "", src, 0)
    if err != nil {
        panic(err)
    }

    // Print the AST.
    ast.Print(fset, f)
}

结果很长就不贴出来了，整个AST的树形结构可以用如下图表示：

同样注意没有扫描出注释，需要的话要将 parser.ParseFile 的最后一个参数改为 parser.ParseComments。再对照如下 ast.File 的定义：

type File struct {
    Doc        *CommentGroup   // associated documentation; or nil
    Package    token.Pos       // position of "package" keyword
    Name       *Ident          // package name
    Decls      []Decl          // top-level declarations; or nil
    Scope      *Scope          // package scope (this file only)
    Imports    []*ImportSpec   // imports in this file
    Unresolved []*Ident        // unresolved identifiers in this file
    Comments   []*CommentGroup // list of all comments in the source file
}

可知上述例子中的 /*comment0*/ 对照结构中的 Doc，是整个 go 文件的描述。和 //comment1 以及 /*comment2*/ 不同，后两者是 Decls 中的结构。

遍历 AST 树

golang 提供了 ast.Inspect 方法供我们遍历整个 AST 树，比如如下例子遍历整个 example/test1.go 文件寻找所有 return 返回的地方：

func TestInspectAST(t *testing.T) {
    // Create the AST by parsing src.
    fset := token.NewFileSet() // positions are relative to fset
    f, err := parser.ParseFile(fset, "./example/test1.go", nil, parser.ParseComments)
    if err != nil {
        panic(err)
    }

    ast.Inspect(f, func(n ast.Node) bool {
        // Find Return Statements
        ret, ok := n.(*ast.ReturnStmt)
        if ok {
            fmt.Printf("return statement found on line %v:\n", fset.Position(ret.Pos()))
            printer.Fprint(os.Stdout, fset, ret)
            fmt.Printf("\n")
            return true
        }
        return true
    })
}

example/test1.go 代码如下：

package main

import "fmt"
import "strings"

func test1() {
    hello := "Hello"
    world := "World"
    words := []string{hello, world}
    SayHello(words)
}

// SayHello says Hello
func SayHello(words []string) bool {
    fmt.Println(joinStrings(words))
    return true  // 16 line
}

// joinStrings joins strings
func joinStrings(words []string) string {
    return strings.Join(words, ", ") // 21 line
}

结果为：

return statement found on line ./example/test1.go:16:2:
return true
return statement found on line ./example/test1.go:21:2:
return strings.Join(words, ", ")

还有另一种方法遍历 AST，构造一个 ast.Visitor 接口：

type Visitor int

func (v Visitor) Visit(n ast.Node) ast.Visitor {
    if n == nil {
        return nil
    }
    fmt.Printf("%s%T\n", strings.Repeat("\t", int(v)), n)
    return v + 1
}

func TestASTWalk(t *testing.T) {
    // Create the AST by parsing src.
    fset := token.NewFileSet() // positions are relative to fset
    f, err := parser.ParseFile(fset, "", "package main; var a = 3", parser.ParseComments)
    if err != nil {
        panic(err)
    }

    var v Visitor
    ast.Walk(v, f)
}

旨在递归地打印出所有的 token 节点，输出：

*ast.File
    *ast.Ident
    *ast.GenDecl
        *ast.ValueSpec
            *ast.Ident
            *ast.BasicLit

AST 的结构定义

通过前述我们知道，抽象语法树有节点(Node)构成，从源代码中(go/ast/ast.go)我们可以看出，Golang 的 AST 主要由三种节点构成：

• 类型节点(Expressions and type nodes)
• 语句节点(statement nodes)
• 声明节点(declaration nodes)。

所有的节点都包含标识其在源代码中开头和结尾位置的信息。

// All node types implement the Node interface.
type Node interface {
    Pos() token.Pos // position of first character belonging to the node
    End() token.Pos // position of first character immediately after the node
}

// All expression nodes implement the Expr interface.
type Expr interface {
    Node
    exprNode()
}

// All statement nodes implement the Stmt interface.
type Stmt interface {
    Node
    stmtNode()
}

// All declaration nodes implement the Decl interface.
type Decl interface {
    Node
    declNode()
}

从代码中看到，所有的 AST 节点都实现了 ast.Node 接口，它只是返回 AST 中的一个位置。

另外，还有3个主要接口实现了 ast.Node。

• ast.Expr - 代表表达式和类型的节点
• ast.Stmt - 代表报表节点
• ast.Decl - 代表声明节点

普通 Node，不是特定语法结构，属于某个语法结构的一部分。

• Comment 表示一行注释 // 或者 /* */
• CommentGroup 表示多行注释
• Field 表示结构体中的一个定义或者变量,或者函数签名当中的参数或者返回值
• FieldList 表示以 {} 或者 () 包围的 Filed 列表

Expression & Types (都划分成 Expr 接口)：类型节点

• BadExpr 用来表示错误表达式的占位符
• Ident 比如包名，函数名，变量名
• Ellipsis 省略号表达式,比如参数列表的最后一个可以写成arg...
• BasicLit 基本字面值,数字或者字符串
• FuncLit 函数定义
• CompositeLit 构造类型,比如{1,2,3,4}
• ParenExpr 括号表达式,被括号包裹的表达式
• SelectorExpr 选择结构,类似于a.b的结构
• IndexExpr 下标结构,类似这样的结构 expr[expr]
• SliceExpr 切片表达式,类似这样 expr[low:mid:high]
• TypeAssertExpr 类型断言类似于 X.(type)
• CallExpr 调用类型,类似于 expr()
• StarExpr 表达式,类似于 X
• UnaryExpr 一元表达式
• BinaryExpr 二元表达式
• KeyValueExp 键值表达式 key:value
• ArrayType 数组类型
• StructType 结构体类型
• FuncType 函数类型
• InterfaceType 接口类型
• MapType map类型
• ChanType 管道类型

Statements ：语句节点

• BadStmt 错误的语句
• DeclStmt 在语句列表里的申明
• EmptyStmt 空语句
• LabeledStmt 标签语句类似于 indent:stmt
• ExprStmt 包含单独的表达式语句
• SendStmt chan发送语句
• IncDecStmt 自增或者自减语句
• AssignStmt 赋值语句
• GoStmt Go语句
• DeferStmt 延迟语句
• ReturnStmt return 语句
• BranchStmt 分支语句 例如break continue
• BlockStmt 块语句 {} 包裹
• IfStmt If 语句
• CaseClause case 语句
• SwitchStmt switch 语句
• TypeSwitchStmt 类型switch 语句 switch x:=y.(type)
• CommClause 发送或者接受的case语句,类似于 case x <-:
• SelectStmt select 语句
• ForStmt for 语句
• RangeStmt range 语句

Declarations 声明节点

• Spec type
• • Import Spec
• • Value Spec
• • Type Spec
• BadDecl 错误声明
• GenDecl 一般声明（和 Spec 相关，比如 import "a",var a,type a）
• FuncDecl 函数声明

Files and Packages

• File 代表一个源文件节点，包含了顶级元素。
• Package 代表一个包，包含了很多文件。

Reference

Cool Stuff With Go’s AST Package Pt 1 How a Go Program Compiles down to Machine Code golang深入源代码系列之一：AST的遍历 Golang的抽象语法树(AST) Step By Step - 刘十一的文章 - 知乎 AST系列(一): 抽象语法树为什么抽象 - Lynnic0x00的文章 - 知乎 何为语法树